package demo;

import java.util.List;

public class SingleLinkedLis {
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;

    public void creatList(){
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;

    }
    //头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }
    //尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null){
            head = node;
            return;
        }
        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index <0 || index > this.size()){
            System.out.println("下标不合法");
        }
        if(index == 0){
            addFirst(data);
        }
        if(index == this.size()){
            addLast(data);
        }

        ListNode node = new ListNode(data);
        ListNode cur = head;
        int n = index;
        while(n - 1 != 0){
            cur = cur.next;
            n--;
        }
        node.next = cur.next;
        cur.next = node;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head == null){
            System.out.println("目标表为空表");
            return;
        }
        if(head.val == key){
            head = head.next;
        }
        ListNode cur = head;
        while(cur.next != null && cur.next.val != key){
            cur = cur.next;
        }
        if(cur.next == null){
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null){
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null){
            if(cur.val == key){
                ListNode curN = cur.next;
                prev.next = curN;
                cur = curN;
            }else{
                cur = cur.next;
                prev = prev.next;
            }
        }
        if(head.val == key){
            head = head.next;
        }
    }
    //得到单链表的长度
    public int size(){
        if(head == null){
            return -1;
        }
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    public void clear() {
        ListNode cur = head;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next =null;
            cur = curN;
        }
        head = null;
    }
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void display(ListNode head){
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //反转链表
    public ListNode reverseList() {
        if(head == null){
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;

    }

    //返回中间节点
    public ListNode middleNode() {
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    //判断链表回文
    public boolean chkPalindrome(ListNode A) {
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;

        while(cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;

        }
        while(slow != A){
            if(slow.val != A.val){
                return false;
            }
            if(A.next == slow){
                return true;
            }
            slow = slow.next;
            A = A.next;
        }
        return true;
    }

    //判断是否有环
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    //拼接两个升序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head1 = list1;
        ListNode head2 = list2;
        ListNode headNew = null;
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        if(head1.val > head2.val){
            headNew = head2;

            head2 = head2.next;
        }else{
            headNew = head1;

            head1 = head1.next;
        }
        ListNode cur = headNew;
        while(head1 != null && head2 != null){
            if(head1.val > head2.val){
                cur.next = head2;
                head2 = head2.next;
            }else{
                cur.next = head1;
                head1 = head1.next;
            }
            cur = cur.next;
        }
        if(head1 == null){
            cur.next = head2;
        }
        if(head2 == null){
            cur.next = head1;
        }
        return headNew;

    }

    //给定值分表
    public ListNode partition(ListNode pHead, int x) {
        // write code here
       ListNode bs = null;
       ListNode be = null;
       ListNode as = null;
       ListNode ae = null;
       while(pHead != null){
           if(pHead.val < x){
               if(bs == null){
                   bs = be = pHead;
               }else{
                   be.next = pHead;
                   be = be.next;
               }

           }else{
               if(as == null){
                   as = ae = pHead;
               }else{
                   ae.next = pHead;
                   ae = ae.next;
               }

           }
           pHead = pHead.next;
       }
        if(as != null){
            ae.next = null;
        }else{
            be.next = null;
        }
        if(bs == null){
            return as;
        }
       be.next = as;

       return bs;
    }

    //相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cura = headA;
        ListNode curb = headB;
        int sizea = 0;
        int sizeb = 0;

        while(cura != null){
            sizea++;
            cura = cura.next;
        }
        while(curb != null){
            sizeb++;
            curb = curb.next;
        }
        cura = headA;
        curb = headB;
        int len = sizeb - sizea;
        if(sizeb - sizea > 0){
            while(len > 0){
                curb = curb.next;
                len--;
            }
        }else{
            len = -len;
            while(len > 0){
                cura = cura.next;
                len--;
            }
        }
        while(cura != null && curb != null){
            if(cura == curb){
                return cura;
            }
            cura = cura.next;
            curb = curb.next;
        }
        return null;
    }

    //找到环的入口
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }

    public ListNode endK(int k){
        ListNode cur = head;
        int len = size() - k;
        while(len != 0){
            cur = cur.next;
            len--;
        }
        return cur;
    }
}
